home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_5.7 / XSGLL / SGLL.C < prev    next >
C/C++ Source or Header  |  1999-09-11  |  11KB  |  369 lines
  1. /* 
  2.  * sgll.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * SGLL
  11.  *
  12.  * construct segm adj list; 
  13.  * version employing shortened segment structure; see also: lsgll.c
  14.  *
  15.  * ms, 11/90;
  16.  * ----------
  17.  * bug fixed in ACCEPT_LEVEL 1: ccurSegm->dij = -ccurSegm->dij:
  18.  * sign had been positive, leading to faulty segment ordering in
  19.  * SGL and subtle error in computed area and length!! ms, 2-26-91;
  20.  */
  21. #include <stdio.h>
  22. #include <string.h>
  23. #include <malloc.h>
  24. #include <math.h>
  25.  
  26. #include "lldef.h"
  27. #include "xsgll.h"
  28.  
  29.  
  30. #undef DEBUG
  31.  
  32.  
  33. /*
  34.  * compare list entries (segments):
  35.  *   key: distance parameter, dij
  36.  *
  37.  */
  38. int
  39. cmpSegmdist (oldSegm, newSegm)
  40.      struct Segmtype *oldSegm, *newSegm;
  41. {
  42.  
  43.   return (SIGN (oldSegm->dij - newSegm->dij));
  44. }
  45.  
  46.  
  47. /*
  48.  * scan list, comparing perpendicular distance dij of newSegm <j>
  49.  * with that of those segments already in current segm adj list (SAL);
  50.  * add newSegm to list: if dij<0, addprev. otherwise add;
  51.  * employs matching function, here cmpSegmdist
  52.  * (see also: llsearch() in llist.c )
  53.  */
  54. Boolean
  55. cmpdij (newSegm, sign_dij, sall)
  56.      struct Segmtype *newSegm;
  57.      int sign_dij;
  58.      struct linklist *sall;
  59. {
  60.   Boolean MatchStatus = False;
  61.  
  62.  
  63.   if (sign_dij > 0) {           /* scan bwd from tail until newdij <= existdij */
  64.     lltail (sall);
  65.     do {
  66.       if (((*sall->match) (sall->clp->item, newSegm)) <= 0)
  67.         MatchStatus = True;
  68.  
  69.     } while ((MatchStatus != True) && (llprevious (sall) == True));
  70.   }
  71.   else {                        /* scan fwd from head until newdij > existdij */
  72.     llhead (sall);
  73.     do {
  74.       if (((*sall->match) (sall->clp->item, newSegm)) > 0)
  75.         MatchStatus = True;
  76.  
  77.     } while ((MatchStatus != True) && (llnext (sall) == True));
  78.   }
  79.  
  80.   return (MatchStatus);
  81. }
  82.  
  83.  
  84. /*
  85.  * to check value of inv overlap pki of segment <k> in SAL<j> with 
  86.  * the reference segment <i>, fetch segm <k>
  87.  */
  88. struct Segmtype *
  89. fetch_segm (csall, sgl_ind)
  90.      struct linklist *csall;
  91.      int sgl_ind;
  92. {
  93.   struct Segmtype *cSegm;
  94.   Boolean MatchStatus = False;
  95.  
  96.   llhead (csall);               /* search SAL for segm <sgl_index> */
  97.   /* skip ref segm at top of list */
  98.  
  99.   while ((llnext (csall) == True) && (MatchStatus != True)) {
  100.     cSegm = (struct Segmtype *) csall->clp->item;
  101.     if (cSegm->segm_ind == sgl_ind)
  102.       MatchStatus = True;
  103.   }
  104.  
  105.   if (MatchStatus == True)
  106.     return (cSegm);
  107.   else
  108.     return ((struct Segmtype *) NULL);
  109. }
  110.  
  111.  
  112. /*
  113.  * scan SAL and check whether active segments remain; 
  114.  * if so, return Active, otherwise set SalStat of the reference 
  115.  * segment of the SAL under inspection to InActive and return InActive
  116.  */
  117. Boolean
  118. check_sal_stat (ActiveSegm, list)
  119.      Boolean *ActiveSegm;
  120.      struct linklist *list;
  121. {
  122.   struct Segmtype *cccSegm, *rrrefSegm;
  123.   Boolean SalStat = InActive;
  124.  
  125.   llhead (list);
  126.   rrrefSegm = (struct Segmtype *) list->clp->item;  /* ref segm at top */
  127.   do {
  128.     cccSegm = (struct Segmtype *) list->clp->item;
  129.     if (*(ActiveSegm + cccSegm->segm_ind) == Active)
  130.       SalStat = Active;
  131.  
  132.   } while ((llnext (list) == True) && (SalStat == InActive));
  133.   rrrefSegm->SalStat = SalStat;
  134.  
  135.   return (SalStat);
  136. }
  137.  
  138.  
  139.  
  140.  
  141. /*
  142.  * expand doubly linked list by adding a segment, maintaining
  143.  * segments in increasing order of dij
  144.  */
  145. void
  146. llexpand (Segm, list)
  147.      struct Segmtype *Segm;
  148.      struct linklist *list;
  149. {
  150.   int s_dij;
  151.  
  152.   llsetmatch (cmpSegmdist, list);
  153.   switch (s_dij = SIGN (Segm->dij)) {
  154.   case -1:
  155.     llhead (list);
  156.     while (cmpdij (Segm, s_dij, list) != True);
  157.     lladdprev ((char *) Segm, list);
  158.     break;
  159.   case 1:
  160.     lltail (list);
  161.     while (cmpdij (Segm, s_dij, list) != True);
  162.     lladd ((char *) Segm, list);
  163.     break;
  164.   case 0:
  165.     printf ("\n...overlap ignored\n");
  166.     break;
  167.   default:
  168.     printf ("\n...unknown SIGN(dij)!\n");
  169.     break;
  170.   }
  171. }
  172.  
  173.  
  174. /* 
  175.  * construct segment group list
  176.  * return number of SGLs containing more than the reference segment
  177.  */
  178. int
  179. construct_sgll (segm, sall, sgll, n_segm, ovlp_thresh)
  180.      struct Segm *segm;
  181.      struct linklist *sall;
  182.      struct linklist *sgll;
  183.      int n_segm;
  184.      double ovlp_thresh;
  185. {
  186.   int n_sgl;
  187.   struct linklist *csall, *ccsall, *cccsall;  /* ptrs to current lists */
  188.   struct linklist *csgll;
  189.   Boolean *ActiveSegm;
  190.  
  191.   struct Segmtype *refSegm, *curSegm;
  192.   struct Segmtype *rrefSegm, *ccurSegm, *cccurSegm;
  193.  
  194.  
  195.   double dij, dji, pij, pji;
  196.   double pki, pkj;
  197.   int i, ref_index;
  198.   int na_segm, naa_segm;
  199.   Boolean SalStat;
  200.  
  201. /*
  202.  * ActiveSegm is an array to globally track the status of segments
  203.  * as they are being assigned to SGLs; each segment mmay only be 
  204.  * be assigned once;
  205.  * Active: segment unassigned
  206.  * InActive: segment assigned
  207.  */
  208.   ActiveSegm = (Boolean *) calloc (n_segm, sizeof (Boolean));
  209.   for (i = 0; i < n_segm; i++)
  210.     *(ActiveSegm + i) = Active;
  211.  
  212.   n_sgl = 0;
  213.   for (i = 0; i < n_segm; i++) {
  214.     csall = (sall + i);
  215.     llhead (csall);             /* ref segm of SAL<i> stored at top */
  216.     refSegm = (struct Segmtype *) csall->clp->item;
  217.     ref_index = i;
  218.     na_segm = 0;
  219.  
  220.  
  221.     if (refSegm->SalStat == Active) {  /* SAL active? */
  222.       csgll = (sgll + i);       /* set current SGL */
  223.       llinit ((char *) refSegm, csgll);  /* init. SGL<i> with ref segm */
  224.  
  225.       ActiveSegm[refSegm->segm_ind] = InActive;
  226.       printf ("\n...SGL<%d> initialized\n", i);
  227.  
  228. /*
  229.  * scan SAL<i>, the SAL of the reference segment:
  230.  * inspect all active segments <j != i> in the SAL; if pji passes 
  231.  * OVLP_THRESH, add <j> to SGL<i> in the order of increasing dij; 
  232.  * when reaching the first segm in SAL<i> for which pji<OVLP_THRESH,
  233.  * stop scanning (pji for all followin segments will be smaller!!) and
  234.  * set na_segm != 0 to signal end of scan;
  235.  * in SGL<i> segments with dij<0 will precede the reference element, 
  236.  * those with dij>0 will follow it
  237.  */
  238.  
  239.       while ((llnext (csall) == True) && (na_segm == 0)) {
  240.         curSegm = (struct Segmtype *) csall->clp->item;
  241.         if (ActiveSegm[curSegm->segm_ind] == Active) {
  242.           if (curSegm->pji > ovlp_thresh) {
  243.             llexpand (curSegm, csgll);
  244.             ActiveSegm[curSegm->segm_ind] = InActive;
  245.           }
  246.           else
  247.             na_segm++;          /* segm remains active */
  248.         }
  249.       }                         /* reached end of cur SAL */
  250.       if (csgll->listlength > 1)
  251.         n_sgl++;                /* count SGLs with more than 1 segm */
  252.  
  253.       if (na_segm == 0)         /* no active segm remaining in SAL<i> */
  254.         refSegm->SalStat = InActive;
  255.  
  256. /*
  257.  * expand SGL<i> if ACCEPT_LEVEL > 0 is indicated:
  258.  *   scan SGL<i>, the segm group list just constructed (segments added to
  259.  *   SGL<i> at that level are considered to satisfy ACCEPT_LEVEL 0);
  260.  *   inspect all active SALs of segments <j> present in SGL<i> (excluding 
  261.  *   SAL<i> which has just been examined); in each SAL<j>, inspect active
  262.  *   elements <k> and compare inverse overlap with OVLP_THRESH:
  263.  *   if pki>OVLP_THRESH: add <k> to SGL<i>
  264.  *   if ACCEPT_LEVEL == 2:
  265.  *           if pji>OVLP_THRESH: add <k> to SGL<i>
  266.  */
  267.       if (ACCEPT_LEVEL > 0) {
  268.         llhead (csgll);         /* scan SGL<i>, inspecting SAL<j> */
  269.         do {
  270.           curSegm = (struct Segmtype *) csgll->clp->item;
  271.           if (curSegm->segm_ind != ref_index) {  /* skip SAL<i> */
  272.             ccsall = &sall[curSegm->segm_ind];  /* fetch SAL<j> */
  273.             llhead (ccsall);    /* ref segm stored at top of SAL */
  274.             rrefSegm = (struct Segmtype *) ccsall->clp->item;
  275.             naa_segm = 0;
  276.  
  277.             if (rrefSegm->SalStat == Active) {  /*scan SAL if actv */
  278.               while (llnext (ccsall) == True) {
  279.                 ccurSegm = (struct Segmtype *) ccsall->clp->item;
  280.                 if (ActiveSegm[ccurSegm->segm_ind] == Active) {
  281.                   cccsall = &sall[ccurSegm->segm_ind];  /* SAL<k> */
  282.                   cccurSegm = fetch_segm (cccsall, ref_index);
  283.  
  284.                   if (cccurSegm != (struct Segmtype *) NULL)
  285.                     pki = (double) cccurSegm->pij;
  286.                   else {
  287.                     pki = -1.0;
  288.                   }
  289.  
  290.                   /* test inverse overlap */
  291.                   /* add segm to SGL if indicated */
  292.                   /* ACCEPT_LEVEL 1 */
  293.                   if (pki > ovlp_thresh) {
  294.                     ccurSegm->dij = -cccurSegm->dij;
  295.                     ccurSegm->pij = cccurSegm->pji;
  296.                     ccurSegm->pji = (float) pki;
  297.                     ccurSegm->sgl_level = 1;
  298.  
  299.                     llexpand (ccurSegm, csgll);
  300.  
  301.                     ActiveSegm[ccurSegm->segm_ind] = InActive;
  302.  
  303.                     llhead (csgll);  /* scan SGL from top */
  304.                   }
  305.                   else if (ACCEPT_LEVEL > 1) {
  306.                     cccurSegm = fetch_segm (cccsall, curSegm->segm_ind);
  307.  
  308.                     if (cccurSegm != (struct Segmtype *) NULL) {
  309.                       pkj = (double) cccurSegm->pij;
  310.                     }
  311.                     else {
  312.                       pkj = -1.0;
  313.                     }
  314.  
  315.                     /* must reevaluate dij, pij, pji */
  316.                     /* with respect to ref segment <i>!! */
  317.                     /* ACCEPT_LEVEL 2 */
  318.                     if (pkj > ovlp_thresh) {
  319.                       prlpar ((segm + ccurSegm->segm_ind)->ptO,
  320.                               (segm + ccurSegm->segm_ind)->ptF,
  321.                               (segm + refSegm->segm_ind)->ptO,
  322.                               (segm + refSegm->segm_ind)->ptF,
  323.                               &dij, &dji, &pij, &pji);
  324. #ifdef DEBUG
  325.                       printf ("\n...returned from prlpar():\n");
  326.                       printf ("    overlap(%d,%d)=%.2lf\n",
  327.                               ccurSegm->segm_ind,
  328.                               refSegm->segm_ind, pij);
  329.                       printf ("    overlap(%d,%d)=%.2lf\n",
  330.                               refSegm->segm_ind,
  331.                               ccurSegm->segm_ind, pji);
  332.                       printf ("  perp.dist(%d,%d)=%.2lf\n",
  333.                               ccurSegm->segm_ind,
  334.                               refSegm->segm_ind, dji);
  335. #endif
  336.                       ccurSegm->dij = (float) dji;
  337.                       ccurSegm->pij = (float) pij;
  338.                       ccurSegm->pji = (float) pji;
  339.                       ccurSegm->sgl_level = 2;
  340.  
  341.                       llexpand (ccurSegm, csgll);
  342.  
  343.                       ActiveSegm[ccurSegm->segm_ind] = InActive;
  344.  
  345.                       /* pro-active check of SAL status: */
  346.                       /* scan SAL<k> to see if actv segm remain */
  347.                       /* if not, mark SAL<k> InActive */
  348.                       SalStat = check_sal_stat (ActiveSegm, cccsall);
  349.  
  350.                       llhead (csgll);  /* scan SGL from top */
  351.                     }
  352.                   }
  353.                   else
  354.                     naa_segm++; /* segm remains active */
  355.                 }
  356.               }                 /* reached end of cur SAL */
  357.               if (naa_segm == 0)  /* no actv segm remain in SAL */
  358.                 rrefSegm->SalStat = InActive;
  359.             }
  360.           }
  361.         } while (llnext (csgll) == True);  /* end of SGL<i> */
  362.       }
  363.     }
  364.   }
  365.   free (ActiveSegm);
  366.  
  367.   return (n_sgl);
  368. }
  369.